#include <bits/stdc++.h>

using namespace std;

// 二叉树打家劫舍问题 ：https://leetcode.cn/problems/house-robber-iii/

// 不需要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution 
{
private:
    struct Info
    {
        int no, yes;
        Info(int a, int b)
        {
            no = a;
            yes = b;
        }
    };

    Info f(TreeNode* x)
    {
        if(x == nullptr) return Info(0, 0);

        Info infol = f(x->left);
        Info infor = f(x->right);
        int no = max(infol.no, infol.yes) + max(infor.no, infor.yes);
        int yes = x->val + infol.no + infor.no;
        return Info(no, yes);
    }

public:
    int rob(TreeNode* root) 
    {
        Info ans = f(root);
        return max(ans.no, ans.yes);
    }
};